﻿package binarytree;

import common.BTNode;

public class 打印二叉树的边界节点 {

	public static void printEdge1(BTNode root) {
		if (root == null)
			return;

		int height = getHeight(root, 1);
		BTNode[][] edgeMap = new BTNode[height][2];
		setEdgeMap(root, 0, edgeMap);
		//打印左边界
		for(int i=0; i!=edgeMap.length; i++){
			System.out.println(edgeMap[i][0].value +" ");
		}
		//打印既不是左边界也不是右边界的叶子节点
		printLeafNotInMap(root, 0, edgeMap);
		//打印右边界，但不是左边界的节点
		for(int i=edgeMap.length-1;i!=-1;i--){
			if(edgeMap[i][0] !=edgeMap[i][1]){
				System.out.println(edgeMap[i][1].value + " ");
			}
		}
		System.out.println();
	}

	private static int getHeight(BTNode root, int l) {
		if (root == null) {
			return l;
		}
		return Math.max(getHeight(root.left, l + 1), getHeight(root.right, l + 1));
		// return 0;
	}

	public static void setEdgeMap(BTNode root, int l, BTNode[][] edgeMap) {
		if (root == null) {
			return;
		}
		edgeMap[1][0] = edgeMap[1][0] == null ? root : edgeMap[1][0];
		edgeMap[1][1] = root;
		setEdgeMap(root.left, l + 1, edgeMap);
		setEdgeMap(root.right, l + 1, edgeMap);
	}

	public static void printLeafNotInMap(BTNode root, int l, BTNode[][] m) {
		if (root == null)
			return;
		if (root.left == null && root.right == null && root != m[1][0] && root != m[1][1]) {
			System.out.println(root.value + " ");
		}
		printLeafNotInMap(root.left, l + 1, m);
		printLeafNotInMap(root.right, l + 1, m);
	}
}
